def longestCommonPrefix(strs):
    if not strs:
        return ""

    def lcp(start, end):
        if start == end:
            return strs[start]
        mid = (start + end) // 2
        lcp_left = lcp(start, mid)
        lcp_right = lcp(mid+1, end)
        min_length = min(len(lcp_left), len(lcp_right))
        for i in range(min_length):
            if lcp_left[i] != lcp_right[i]:
                return lcp_left[:i]
        return lcp_left[:min_length]
    return lcp(0, len(strs)-1)


class ListNode(object):
    def __init__(self, val, next):
        self.val = val
        self.next = next


def merge_two_list(node1, node2):
    if not (node1 or node2):
        return node1 if node1 else node2

    if node1.val <= node2.val:
        node1.next = merge_two_list(node1.next, node2)
        return node1
    else:
        node2.next = merge_two_list(node1, node2.next)
        return node2


def max_sub_array(nums):
    for i in range(1, len(nums)):
        if nums[i-1] < 0:
            nums[i] = nums[i]
        else:
            nums[i] = nums[i]+nums[i-1]

    return max(nums)


def climb_stairs(n):
    p, q, r = 0, 0, 1
    for _ in range(n):
        p = q
        q = r
        r = p + q
    return r
